#include<iostream>
using namespace std;
const int N = 510;
int g[N][N];
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	/*int z = 1;
	int ans = 0;
	for (int k = 1; k <= n; k++) {
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (k == z)continue;
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				sum += g[i][j];
			}
		}
		ans += sum / 2;
		z++;
	}
	cout << ans << endl;*/
	int ans = 0;
	for (int k = n; k >= 1; k--) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				if (i >= k && j >= k)ans += g[i][j];
			}
		}
	}
	cout << ans << endl;
	return 0;
}